// 2025/11/8
// 最小覆盖子串

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> cnt;
        for(auto ch : t)
            ++cnt[ch];
        int l = 0, r = 0, n = s.size(), ok_cnt = 0;
        int ans_begin = 0, ans_size = n;
        bool flag = false;
        for(r = 0; r < n; r++)
        {
            if(cnt.count(s[r]))
            {
                if(--cnt[s[r]] == 0 && ++ok_cnt == cnt.size())
                {
                    flag = true;
                    while(!(cnt.count(s[l]) && ++cnt[s[l]] > 0))
                        l++;
                    ok_cnt--;
                    if(r - l + 1 < ans_size)
                    {
                        ans_begin = l;
                        ans_size = r - l + 1;
                    }
                    l++;
                }
            }
        }
        if(flag)
            return s.substr(ans_begin, ans_size);
        else
            return "";
    }
};